package com.example.question.dp.dp2;

import com.example.question.tree.tree1.Tree;
import com.example.question.tree.tree1.TreeNode;

/**
 * @Date 2023-07-22
 * @Author Jonathan
 */
public class Code05_337 {
    public static void main(String[] args) {
        TreeNode tree = Tree.createTree(new Integer[]{3, 2, null, 3, null, null, 3, null, 1, null, null});
//        TreeNode tree = Tree.createTree(new Integer[]{3, 4, 1, null, null, 3, null, null, 5, null, 1, null, null});
        Code05_337 code = new Code05_337();
        int rob = code.rob(tree);
        System.out.println(rob);
    }


    public int rob1(TreeNode root) {
        int[] helper = dfs1(root);
        return Math.max(helper[0], helper[1]);
    }


    private int[] dfs1(TreeNode node) {
        if (node == null) return new int[2];
        int[] left = dfs1(node.left);
        int[] right = dfs1(node.right);
        int[] result = new int[2];
        // 不偷当前节点
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前节点
        result[1] = left[0] + right[0] + node.val;
        return result;

    }

    public int rob(TreeNode root) {
        Helper helper = dfs(root);
        return Math.max(helper.val1, helper.val2);
    }

    /**
     * 这个递归该怎么写呢？
     * 这个的效率高一些  减少了计算
     */
    private Helper dfs(TreeNode node) {
        if (node == null) {
            return null;
        }
        Helper left = dfs(node.left);
        Helper right = dfs(node.right);
        // 叶子节点
        if (left == null && right == null) {
            // 偷的话就是node自己的值 因为此时就是叶子节点
            return new Helper(node.val, 0);
        }
        if (left == null) {
            return new Helper(node.val + right.val2, Math.max(right.val1, right.val2));
        }
        if (right == null) {
            return new Helper(node.val + left.val2, Math.max(left.val1, left.val2));
        }
        // 不要当前节点的时候 孩子节点是否需要还要进行比较才知道
        return new Helper(node.val + right.val2 + left.val2, Math.max(left.val1, left.val2) + Math.max(right.val1, right.val2));
    }


    /**
     * 这个的效率比较低
     * @param node
     * @return
     */
    private Helper dfs2(TreeNode node) {
        if (node == null) {
            return new Helper(0, 0);
        }
        Helper left = dfs2(node.left);
        Helper right = dfs2(node.right);
        // 叶子节点
        // 不要当前节点的时候
        return new Helper(node.val + right.val2 + left.val2, Math.max(left.val1, left.val2) + Math.max(right.val1, right.val2));
    }

    static class Helper {
        // 偷node节点的值时 以node为根节点的最大值
        int val1;
        // 不偷node节点的值时 以node为根节点的最大值
        int val2;

        public Helper(int val1, int val2) {
            this.val1 = val1;
            this.val2 = val2;
        }
    }

}
